package com.zhugang.week13.hash;

import java.util.HashSet;
import java.util.Set;

/**
 * @program algorithms
 * @description: getIntersectionNode
 * @author: chanzhugang
 * @create: 2022/12/02 19:48
 */
public class GetIntersectionNode {

    /**
     * 160 相交链表
     * https://leetcode.cn/problems/intersection-of-two-linked-lists/
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 哈希集合缓存其中一个链表
        Set<ListNode> set = new HashSet<>();
        ListNode p = headA;
        while (p != null) {
            set.add(p);
            p = p.next;
        }
        p = headB;
        while (p != null) {
            if (set.contains(p)) {
                return p;
            }
            p = p.next;
        }
        return null;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        // 不好想，想出来了锻炼链表代码的编写能力
        // 长的链表先走｜la - lb｜，之后一起走
        ListNode pA = headA;
        int lA = 0;
        while (pA != null) {
            lA++;
            pA = pA.next;
        }
        ListNode pB = headB;
        int lB = 0;
        while (pB != null) {
            lB++;
            pB = pB.next;
        }

        pA = headA;
        pB = headB;
        // 长的链表先走
        if (lA >= lB) {
            for (int i = 0; i < lA - lB; i++) {
                pA = pA.next;
            }
        } else {
            for (int i = 0; i < lB - lA; i++) {
                pB = pB.next;
            }
        }
        // 遍历只要不想等，一直next
        while (pA != null && pB != null && pA != pB) {
            pA = pA.next;
            pB = pB.next;
        }
        if (pA == null || pB == null) {
            return null;
        }
        return pA;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}